package com.xyhuo.leetcode.y2025;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DiffWaysToCompute {

    public static void main(String[] args) {
        DiffWaysToCompute d = new DiffWaysToCompute();
        d.diffWaysToCompute("2*3-4*5");
    }

    public List<Integer> diffWaysToCompute(String expression) {
        List<String> analyse = analyse(expression);
        List<Integer> ans = cal(analyse, 0, analyse.size() - 1);
        return ans;
    }

    private List<Integer> cal(List<String> list, int left, int right) {
        List<Integer> ans = new ArrayList<>();
        if (left == right) {
            ans.add(Integer.valueOf(list.get(left)));
            return ans;
        }
        for (int i = left; i <= right; i++) {
            String s = list.get(i);
            if ("+".equals(s) || "-".equals(s) || "*".equals(s)) {
                List<Integer> leftList = cal(list, left, i - 1);
                List<Integer> rightList = cal(list, i + 1, right);
                for (Integer t1 : leftList) {
                    for (Integer t2 : rightList) {
                        Integer value = calculate(s, t1, t2);
                        ans.add(value);
                    }
                }
            }
        }
        return ans;
    }

    private Integer calculate(String sign, Integer n1, Integer n2) {
        int ans = 0;
        if ("+".equals(sign)) {
            ans = n1 + n2;
        } else if ("-".equals(sign)) {
            ans = n1 - n2;
        } else if ("*".equals(sign)) {
            ans = n1 * n2;
        }
        return ans;
    }

    private List<String> analyse(String exp) {
        List<String> list = new ArrayList<>();
        char[] charArray = exp.toCharArray();
        int lastIndex = 0;
        for (int i = 1; i < charArray.length; i++) {
            if (charArray[i] == '+' || charArray[i] == '-' || charArray[i] == '*' || charArray[i] == '/') {
                String num = exp.substring(lastIndex, i);
                list.add(num);
                list.add(String.valueOf(charArray[i]));
                lastIndex = i + 1;
            }
        }
        list.add(exp.substring(lastIndex));
        return list;
    }
}
